1. Field of the Invention
The present invention relates to an identification information embedding apparatus which embeds a collusion-secure code indicative of identification information of an object in an object of, e.g., a copy of digital contents, and an identification information analysis apparatus which detects a collusion-secure code from an object and analyzes identification information.
2. Description of the Related Art
Digital contents (for example, a still picture, a moving picture, sound, music and others) include a plurality of items of digital data. Of the many kinds of data, there are some which can maintain the identity or the economic value of a work of the digital contents even if they are changed to some degree. By changing data which falls in such an allowable range, various kinds of information can be embedded in the digital contents. Such a technique is referred to as an electronic watermark.
With the electronic watermark technique, it is possible to embed various kinds of watermark information (for example, information to identify a copyright holder or a user of contents, information of rights of a copyright holder, conditions to utilize contents, confidential information required when utilizing contents, a copy control information and the like, combinations of such information and others) for variety of purposes (for example, control over utilization, copyright protection including copy control, promotion of secondary use and others) and detect/use them.
Here, consideration is given as to the application of the electronic watermark technique to embed information which individually identifies a copy (for example, watermark information uniquely corresponding to a user ID) when distributing these copies of the digital contents to many users.
A technique to embed (a code corresponding to) inherent identification information in a copy of digital contents functions to avoid an illegal copy of the digital contents and also serves as a post-relief when violation of the copyright occurs since a user who further duplicates a copy of the digital contents and runs it off as a pirate edition can be specified by detecting identification information from the pirate edition when this pirate edition goes into circulation.
Such a user tries to interpolate the identification information when creating the pirate edition. However, since the user does not know which part corresponds to bits forming (a code corresponding to) the identification information, he/she must considerably change the copy of the digital contents. By doing so, since the economic merit of the digital contents is lost, the motivation to illegally copy is diminished.
In such a circumstance, a “collusion attack” has emerged as a method which enables illegal copying.
The collusion attack utilizes the fact that different identification information is embedded in each copy. For example, by this method, when a plurality of people bring copies and compare them bit by bit, a part having a different value of digital data (embedded identification information) is found, and the identification information is changed and lost by changing only this part (for example, majority decision, minority decision, randomization and others). It is to be noted that a similar result may be obtained in some cases by performing an operation, e.g., averaging pixel values between the contents without effecting a specific comparison operation.
For instance, giving a simple example, it is assumed that (codes corresponding to) the following identification information are embedded in copies of Mr./Ms. A, Mr./Ms. B and Mr./Ms. C, respectively:                A: 00 . . . 00 . . .        B: 00 . . . 11 . . .        C: 11 . . . 00 . . .When the part of the identification information is detected, this part can be changed into, e.g., (a code corresponding to) the following identification information which is different from that of each of Mr./Ms. A, Mr./Ms. B and Mr./Ms. C:        10 . . . 01 . . .        
Therefore, there have been proposed various kinds of method which embed a code having a resistance to a collusion attack, i.e., a property capable of specifying a part or all of colluders even if under the collusion attack (which will be referred to as a collusion-secure code hereinafter) as an electronic watermark and a tracing algorithm based on the collusion-secure code (algorithm used to specify an identification number embedded in contents used for a collusion attack and specify user IDs of the colluders). For example, there is (1) Dan Boneh and James Shaw, “Collusion-Secure Fingerprinting for Digital Data,” CRYPTO 195, 452-465, 1995 or (2) Hirofumi Muratani, “A Collusion-Secure Fingerprinting Code Reduced by Chinese Remaindering and Its Random-Error Resilience”, Information Hiding Workshop 2001, 303-315, 2001.
The collusion-secure code disclosed in the cited reference (1) is defined as a code that there is a tracing algorithm which outputs at least one collusion ID belonging to C with respect to an arbitrary collusion C which is |C|≦c (c is the maximum number of collusions, i.e., a total number of colluders). In order to further strengthen the resistance to the collusion attack, namely, further increase the upper limit number of the number of collusions which disables specification of colluders, a code length to be embedded in the contents must be increased. On the other hand, since there is a limit in a code length to be embedded in contents, an upper limit is provided in the number of copies utilized for collusion attack in order to reduce a code length in this kind of collusion-secure code and the tracing algorithm based on this collusion-secure code. If the collusion attack is carried out using copies whose number exceeds an allowed number, there may occur an erroneous judgment that an identification number of a copy which does not concern the collusion attack is erroneously output as an identification number of a copy which has concerned the collusion attack and a person who is not a colluder is specified as a colluder.
In order to lower the probability of the erroneous judgment, the number of copies which are realistically likely to be prepared by colluders is assumed, a collusion-secure code must be designed in such a manner that an allowed number exceeds that number, and a large allowable number must be absolutely set, which leads to a large code length.
An attempt to decrease the code length is the cited reference (2). This code is a code with which reduction in code length is considerable when a total number of sets of identification information or a collusion size is large. This code has a structure of a “concatenated code” utilizing “Chinese Remainder Theorem” and allows a tracing error in not only an “inner code” but also an “outer code”. In order to estimate a tracing error rate in an outer code, as a new “marking assumption,” it is assumed that “respective residues forming a set of residue pairs obtained by decoding the inner code relative to a code word created by a collusion can be treated as random variables which take a value with probabilities in conformity with an independent and uniform distribution.” The number of inner codes is determined in such a manner that a probability that a person who is not a colluder is accidentally regarded as a colluder with respect to a residue pair obtained from a predetermined number or more of the inner codes.
However, a problem in the cited reference (2) is that a reasonable ground is not provided to this assumption and the outer code formed by the stochastic argument based on this requires many inner codes with respect to a small c. Therefore, the number d of the inner codes cannot be suppressed relative to a small c, and the number of tracing errors with respect to the outer codes cannot be zero.